package com.cqs.leetcode;

/**
 * Author:li
 * <p>
 * create date: 18-6-5 14:13
 */
public class DivideTwoIntegers {

    public int divide(int dividend, int divisor) {
        if (divisor == Integer.MIN_VALUE) {
            return dividend == Integer.MIN_VALUE ? 1 : 0;
        }
        int absResult = 0;
        //边界处理
        if (dividend == Integer.MIN_VALUE) {
            if (divisor == -1) return Integer.MAX_VALUE;
            absResult = 1;
            if (divisor > 0) {
                dividend = dividend + divisor;
            } else {
                dividend = dividend - divisor;
            }
        }
        //符号处理
        int sign = (dividend >> 31) ^ (divisor >> 31);
        //先全部非负数处理
        if (dividend < 0) {
            dividend = -dividend;
        }
        if (divisor < 0) {
            divisor = -divisor;
        }
        absResult += divide0(dividend, divisor);
        return sign == 0 ? absResult : -absResult;
    }

    private int divide0(int dividend, final int divisor) {
        int sum = 0;
        if (dividend < divisor) return sum;
        int i = 1;
        int nd = divisor;
        while (dividend >= nd && nd > 0) {
            //注意nd>0的条件 当Integer.MAX_VALUE / 1的时候 nd在最后会出现负数
            dividend -= divisor * i;
            sum += i;
            nd = nd << 1;//翻倍
            i = i << 1;
        }
        if (dividend >= divisor) {
            sum += divide(dividend, divisor);
        }
        return sum;
    }

    public static void main(String[] args) {
        DivideTwoIntegers d = new DivideTwoIntegers();
//        System.out.println(Integer.toHexString(Integer.MIN_VALUE) + "\t" + (Integer.MIN_VALUE & 0x7fffffff));
        System.out.println(d.divide(Integer.MIN_VALUE + 100, -2147483648));
    }
}
